package sword_offer;

/**
 * @author Synhard
 * @version 1.0
 * @Class sword_offer.Code15
 * @Description 实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，x^n）。不得使用库函数，同时不需要考虑大数问题。
 * @tel 13001321080
 * @email 823436512@qq.com
 * @date 2021-03-14 15:39
 */
public class Code15 {

    public static void main(String[] args) {
        System.out.println(myPow(2.00000D, 10));
        System.out.println(myPow(2.10000D, 3));
        System.out.println(myPow(2.00000D, -2));
    }

    public static double myPow(double background, long exponent) {
        if (exponent < 0) { // 指数为负数
            background = 1 / background;
            exponent = -exponent;
        }
        return getRes(background, exponent);
    }

    // 快速幂算法
    public static double getRes(double background, long exponent) {
        if (exponent == 0) {
            return 1;
        }
        double tempt = getRes(background, exponent >> 1);
        if ((exponent & 1) == 1) {
            return tempt * tempt * background;
        }
        return tempt * tempt;
    }
}
/*
快速幂算法的思想就是将N个数连乘化简至近似于只需要求N/2个数相乘，
即将时间复杂度从O(N)化为O(log2N)
需要注意的是，以后乘2除2 使用位运算符
判断是不是偶数使用(exponent & 1) == 1 来进行判断
 */